package com.剑指offer.第三章;

import java.util.HashMap;

/**
 *使用哈希表记录t1中的所有字符出现的次数  当所有字符的出现的次数都小于0时，就说明包含了t中的所有字符。
 * 使用两个指针
 * 如果没有包含t的所有字符，就移动第二个指针，直到包含为止。
 * 如果某一时刻两个指针之间的子字符串已经包含了t的所有字符，就移动第一个指针，移动之后仍然包含t的所有字符串 就继续移动第一个指针
 */
public class 包含所有字符的最短字符串 {

    public static String resolve(String s1, String t1) {
        HashMap<Character, Integer> counts = new HashMap<>();

        for (char c : t1.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int i = 0, j = 0;
        int minStart = 0, minEnd = 0;
        int minLenth = Integer.MAX_VALUE;
        for (; i < s1.length(); i++) {
            counts.put(s1.charAt(i), counts.getOrDefault(s1.charAt(i), 0) - 1);
            while (isLess0(counts)) {
                if (i - j + 1 < minLenth) {
                    minStart = j;
                    minEnd = i;
                    minLenth = Math.min(i - j + 1, minLenth);

                }
                counts.put(s1.charAt(j), counts.getOrDefault(s1.charAt(j), 0) + 1);
                j++;
            }
        }

        return minLenth < Integer.MAX_VALUE ? s1.substring(minStart, minEnd + 1) : "";
    }

    public static boolean isLess0(HashMap<Character, Integer> counts) {
        for (Integer value : counts.values()) {
            if (value > 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(resolve("ADDNCAD", "ADD"));
    }

}
